/*
 * pml_bg.c
 *
 *  Created on: 2013幄1�7�1�7�1�7�1�7�1�7�1�7�1�7�1�7�1�7�1�7�1�7�1�7*      Author: lius
 */


#include <stdio.h>
#include <stdlib.h>
#include "pml_bg.h"
#include "pml_qgram_grade.h"

static const int alphabet_size = 256;

#define MAX_Q_SIZE 3
#define MIN_Q_SIZE 1
#define MAX_M_SIZE 8
#define MIN_M_SIZE 3

//static int q_size = 2;
//static int q_gram_size = 4;
//static int m_size = 8;


static int recurbinary(pml_sub_pat  *a, pml_sub_pat  key, int low, int high)
{
	int mid;
	if (low > high)
		return -1;
	mid = (low + high) / 2;
	if (a[mid] == key)
		return mid;
	else if (a[mid] > key)
		return recurbinary(a, key, low, mid - 1);
	else
		return recurbinary(a, key, mid + 1, high);
}

char* Char2HexString(char a)
{
	static char res[3] = {};
	int i=1,j=0;
	char tmp;
	for(i=1,j=0;i>=0;i--,j++){
		tmp = (a>>i*4) & 0x0f;
		switch(tmp)
		{
		case 0:
			res[j] = '0';
			break;
		case 1:
			res[j] = '1';
			break;
		case 2:
			res[j] = '2';
			break;
		case 3:
			res[j] = '3';
			break;
		case 4:
			res[j] = '4';
			break;
		case 5:
			res[j] = '5';
			break;
		case 6:
			res[j] = '6';
			break;
		case 7:
			res[j] = '7';
			break;
		case 8:
			res[j] = '8';
			break;
		case 9:
			res[j] = '9';
			break;
		case 10:
			res[j] = 'a';
			break;
		case 11:
			res[j] = 'b';
			break;
		case 12:
			res[j] = 'c';
			break;
		case 13:
			res[j] = 'd';
			break;
		case 14:
			res[j] = 'e';
			break;
		case 15:
			res[j] = 'f';
			break;
		}
	}
	return (res);
}



static inline unsigned int hash_32(unsigned int val, unsigned int bits)
{
	#define GOLDEN_RATIO_PRIME_32 0x9e370001UL
	/* On some cpus multiply is faster, on others gcc will do shifts */
	unsigned int hash = val * GOLDEN_RATIO_PRIME_32;
	/* High bits are more random, so use them. */
	return hash >> (32 - bits);
	//return (hash & 0x1FFFFF);
	//char *p = (char*)&val;
	//((((((unsigned int)p[0]) & 0x7F)<<14)|((((unsigned int)p[1]) & 0x7F)<<7)|(((unsigned int)p[2]) & 0x7F)))
}



int pml_bg_init(pml_bg *pbg, int m_size, int q_size, int groups, int limit_score)
{
	//if(q > MAX_Q_SIZE || q < MIN_Q_SIZE)
	//	return -1;
	q_size = (q_size>MAX_Q_SIZE?MAX_Q_SIZE:q_size);
	int q_gram_size = q_size;

	memset(pbg, 0x00, sizeof(pml_bg));

	pbg->q_size = q_size;
	pbg->m_size = m_size;
	pbg->q_gram_size = q_gram_size;
	pbg->limit_score = limit_score;
	pbg->act_bits = pbg->m_size - pbg->q_gram_size + 1;
	pbg->max_shift = pbg->m_size - pbg->q_gram_size;
	pbg->groups = groups;

	//int size = ((m_size%8)?(m_size/8 + 1):(m_size/8)) * (1 << (q_size*8>21?21:q_size*8));
	int size = 1 << (q_size*8>21?21:q_size*8);

	pbg->shift_table = calloc(size, 1);

	pbg->pat_array = calloc(size, sizeof(pat_stat_node));
	pbg->all_pat_array = calloc(size, sizeof(pat_stat_node));
	pbg->all_dst_array = calloc(size, sizeof(pat_stat_node));
	pbg->array_size = size;

	//pbg->pat_list = clist_new();

	return 0;
}


static int my_compar(const void *a, const void *b)
{
	pml_sub_pat  *pst_1 = a;
	pml_sub_pat  *pst_2 = b;
	if(*pst_1 > *pst_2)
		return 1;
	else if (*pst_1 == *pst_2)
		return 0;
	else
		return -1;
}

int pml_bg_pre_match(pml_bg *pbg)
{
	qsort(pbg->sub_pat.pat_array, pbg->sub_pat.pat_num, sizeof(pml_sub_pat),my_compar);
	return 0;
}


int pml_bg_exit(pml_bg *pbg)
{
	return 0;
}



static inline unsigned int get_gram(int q_gram_size, char *p)
{
	#define qual_grams(p)   ((unsigned int)p[0])
	#define triple_grams(p) (((((unsigned int)p[0]) & 0x7F)<<14)|((((unsigned int)p[1]) & 0x7F)<<7)|(((unsigned int)p[2]) & 0x7F))
	//#define triple_grams(p) (((((unsigned int)p[0]) & 0xFF)<<13)|((((unsigned int)p[1]) & 0xFF)<<5)|(((unsigned int)p[2]) & 0xFF))
	#define double_grams(p) ((unsigned short)*((unsigned short*)p))
	#define single_grams(p) ((unsigned char)p[0])

	if(q_gram_size == 1)
		return single_grams(p);
	else if(q_gram_size == 2)
		return double_grams(p);
	else if(q_gram_size == 3)
		return triple_grams(p);
	else if(q_gram_size == 4)
		return hash_32(qual_grams(p), 21);
}

static inline unsigned int set_shift_pos(pml_bg *pbg, char *str, unsigned int gram, unsigned int pos)
{
	unsigned char *p = (unsigned char *)pbg->shift_table;
	int i;
	unsigned char mask = 1 << pos;
	//int max = pbg->m_size-pbg->q_gram_size+1;
	//for(i = 1; i < max - pos; i ++)
	//	mask |= mask<<1;
	p[gram] |= mask;
	//printf("set [%d][%x][%x][%d]\n", gram, p[gram], mask, pos);
	memcpy(pbg->pat_array[gram].grams, str, pbg->q_gram_size);
	pbg->pat_array[gram].pos_count[pos] ++;
	pbg->pat_array[gram].count_all ++;
	return p[gram];
}

static inline unsigned int get_shift_pos(pml_bg *pbg, unsigned int gram)
{
	unsigned char *p = (unsigned char *)pbg->shift_table;

//	FILE *fp = fopen("./lpppp.txt", "ab+");
//	fprintf(fp, "%d\n", gram);
//	fclose(fp);
//	return 0;

	//printf("get [%d][%x]\n", gram, p[gram]);
	//return (p[gram] &= 1<<pos);
	return (p[gram]);
}


int pml_bg_add_pat(pml_bg *pbg, char*p, int len)
{
//	FILE *fp = fopen("./lpppp.txt", "ab+");
//	fwrite(p, 1, len,fp);
//	fwrite("\n", 1, 1,fp);
//	fclose(fp);
//	return 0;
	int m_size = pbg->m_size;
	if(len < m_size)
		return -1;

	int q_gram_size = pbg->q_gram_size;
	double score;
	int pos = pml_qgram_select(p, len, m_size, q_gram_size, &score);
	if(score < (double)pbg->limit_score)
	{
		int i;
		for(i = 0;i < len; i++)
			fprintf(stdout, "%s", Char2HexString(p[i]));
		fprintf(stdout, "\n");
		return -2;
	}

	p += pos;

	int i;
	unsigned int gram;
	int offset;

	unsigned int gram_num = len - q_gram_size + 1;
	//unsigned int *gram_array = malloc(gram_num*sizeof(int));
	for(i = 0;i < gram_num; i++)
	{
		gram = get_gram(q_gram_size, &p[i]);
		if(gram>pbg->array_size)
			printf("----------\n");
		pbg->all_pat_array[gram].count_all ++;
		memcpy(pbg->all_pat_array[gram].grams, &p[i], q_gram_size);
	}

	//offset = (len - m_size)>0?(len - m_size - 1):(len - m_size);
	offset = 0;
	//printf("%d,%d\n", offset, len);

	pbg->sub_pat.pat_array[pbg->sub_pat.pat_num++] = pml_sub_pat_conv(p);

	for(i = pbg->max_shift; i>=0; i--)
	{
		gram = get_gram(q_gram_size, &p[i + offset]);
		//printf("gram:[%d][%c][%c]\n", gram, p[i], p[i+1]);
		set_shift_pos(pbg, &p[i + offset], gram, pbg->max_shift - (i));
	}

//	FILE *fp = fopen("./lpppp.txt", "ab+");
//	for(i = 0;i < m_size; i++)
//		fprintf(fp, "%s", Char2HexString(p[i]));
//	fprintf(fp, "\n");
//	fclose(fp);

	return 0;
}



static int compar(const void *a, const void *b)
{
	pat_stat_node *pst_1 = a;
	pat_stat_node *pst_2 = b;
	if(pst_1->count_all > pst_2->count_all)
		return -1;
	else if (pst_1->count_all == pst_2->count_all)
		return 0;
	else
		return 1;
}

static void pml_print_static(pml_bg *pbg, pat_stat_node *pat_array)
{
	int i = 0;
	int top  = 100;//pbg->array_size
	int q_gram_size = pbg->q_gram_size;
	qsort(pat_array, pbg->array_size, sizeof(pat_stat_node),compar);
	printf("index, gram, HEX, STRING, POS0, POS1, POS2, POS3, POS4, POS5, POS6, POS7, SUM\n");
	for(i = 0; i < top; i++)
	{
		if(!pat_array[i].count_all)
			continue;
		printf("%05d,%07d,", i, get_gram(q_gram_size, pat_array[i].grams));
		pat_array[i].grams[4] = 0;
		int j = 0;
		for(j = 0;j < q_gram_size; j++)
			printf("%s", Char2HexString(pat_array[i].grams[j]));
		printf(",");
		printf("%.*s,", q_gram_size, pat_array[i].grams);
		for(j = 0;j<8;j++)
			printf("%d,", pat_array[i].pos_count[j]);
		printf("%d\n", pat_array[i].count_all);
	}

}


static void pml_bg_static(pml_bg *pbg)
{
	//static empty count
	char tmp_gram[5] = {0xFF,0xFF,0xFF,0xFF,0x00};
	int i = 0;
	int empty_mask_count = 0;
	for(; i < get_gram(pbg->q_gram_size, tmp_gram); i++)
	{
		if(!get_shift_pos(pbg, i))
			empty_mask_count++;
	}
	printf("all_mask_count::[%d],valid_mask_count:[%d]\n", get_gram(pbg->q_gram_size,tmp_gram), get_gram(pbg->q_gram_size,tmp_gram) - empty_mask_count);

	//static grams count
	pml_print_static(pbg, pbg->pat_array);
	pml_print_static(pbg, pbg->all_pat_array);
	pml_print_static(pbg, pbg->all_dst_array);
}

static int pml_verify_match(pml_bg *pbg, char *buff)
{
	int ret = recurbinary(pbg->sub_pat.pat_array, pml_sub_pat_conv(buff), 0, pbg->sub_pat.pat_num);
	if(ret>=0)
	{
		printf("--------------------%.*s-------------------\n", pbg->m_size, buff);
		pbg->hit_count++;
	}
//	int j;
//	for(j = 0;j < pbg->m_size; j++)
//		printf("%s", Char2HexString(buff[j]));
//	printf("\n");
	pbg->verify_count++;
	return 0;
}

int pml_bg_match(pml_bg *pbg, char * buff, int len)
{
	//bgMatcher(T, n)
	int i = 0;
	int m_size = pbg->m_size;
	int q_gram_size = pbg->q_gram_size;
	int init_val = pbg->max_shift;
	int shift = 0;
	double avg_shift = 0;
	int shift_count  = 0;
	int shift_steps = 0;

//	unsigned int gram_num = len - q_gram_size + 1;
//	for(i = 0;i < gram_num; i++)
//	{
//		unsigned int gram = get_gram(&buff[i]);
//		pbg->all_dst_array[gram].count_all ++;
//		memcpy(pbg->all_dst_array[gram].grams, &buff[i], q_gram_size);
//	}
//
//	pml_bg_static(pbg);

	i = 0;
	while(i < len-m_size)
	{
		int j = init_val;
		unsigned char D = 0xFF;
		while (1)
		{
			unsigned char Di = get_shift_pos(pbg, get_gram(q_gram_size, &buff[i+j]));
			if (!(D &= Di))
			{
				shift = i+j+1;
				break;
			}
			else if (j == 0)
			{
				pml_verify_match(pbg, &buff[i]);
				shift = i+1;
				break;
			}
			else
			{
				//printf("[%d][%c][%c]\n", i+j, buff[i+j], buff[i+j+1]);
				j = j-1;
				D = D << 1;
			}
		}

		//avg_shift = ((avg_shift*shift_count) + (shift-i))/(++shift_count);
		shift_count++;
		shift_steps += shift-i;
		i = shift;
	}
	pbg->shift_count = shift_count;
	pbg->avg_shift = (double)shift_steps/shift_count;
	return 0;
}
